package com.changlu._02二维数组中查找目标值;

/**
 * @ClassName PrombleSoleve
 * @Author ChangLu
 * @Date 2022/2/16 19:03
 * @Description 二维数组查找目标值题解
 */
public class ProblemSolve {

    /**
     * 方式一：标志数筛检法(时间最优)
     *      时间复杂度O(m+n)、空间复杂度O(1)
     * @param matrix
     * @param target
     * @return
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int row = matrix.length - 1;
        int col = 0;
        //n*m的二维数组：matrix.length为n，matrix[0].length为m
        while (row >= 0 && col < matrix[0].length) {
            if (target > matrix[row][col]){
                col++;
            }else if (target < matrix[row][col]){
                row--;
            }else{
                return true;
            }
        }
        return false;
    }

}